package com.mdnote.jianzhi_offer.tree;

/**
 * @author Rhythm-2019
 * @version 1.0
 * @date 2020/10/11
 * @description 剑指 Offer 07. 重建二叉树
 */
public class Offer07 {


    public static void main(String[] args) {
        Offer07 offer07 = new Offer07();
//        TreeNode treeNode = offer07.buildTree(new int[]{3, 9, 20, 15, 7}, new int[]{9, 3, 15, 20, 7});
        TreeNode treeNode = offer07.buildTree(new int[]{5}, new int[]{5});
        System.out.println(treeNode);
    }

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder.length == 0 || inorder.length == 0) {
            return null;
        }

        return rebuild(preorder, 0, preorder.length - 1,
                inorder, 0, inorder.length - 1);
    }

    private TreeNode rebuild(int[] preorder, int preStart, int preEnd, int[] inorder, int inSStart, int inEnd) {

        // Terminatpr
        if (preStart > preEnd || inSStart > inEnd) {
            return null;
        }

        // Process
        TreeNode treeNode = new TreeNode(preorder[preStart]);
        // 在中序遍历数组的缩影
        int inIndex = findInOrde(inorder, preorder[preStart], inSStart, inEnd);

        int leftSize = inIndex - inSStart + 1;
        // Drill down
        treeNode.left = rebuild(preorder, preStart + 1, preStart + leftSize - 1,
                inorder, inSStart, inIndex - 1);
        treeNode.right = rebuild(preorder, preStart + leftSize, preEnd,
                inorder, inIndex + 1, inEnd);


        // Restore data
        return treeNode;
    }

    private int findInOrde(int[] inorder, int val, int inStart, int inEnd) {
        for (int i = inStart; i <= inEnd; i++) {
            if (inorder[i] == val) {
                return i;
            }
        }
        return -1;
    }


    public static class TreeNode {
          int val;
          TreeNode left;
          TreeNode right;
          TreeNode(int x) { val = x; }
      }
    }
